package hot;

import java.util.ArrayList;
import java.util.List;

public class yisanyi {

        static String s=new String();
        static List<List<String>> ret=new ArrayList<>();
        static List<String> path=new ArrayList<>();
        public static List<List<String>> partition(String _s) {
            s=_s;
            dfs(0);
            return ret;
        }
        public static void dfs(int pos){
            if(pos==s.length()){
                ret.add(new ArrayList(path));
                return;
            }
            for(int i=pos;i<s.length();i++){
                String substr=s.substring(pos,i+1);
                //如果是回文串的话
                if(isPalindrome(substr)){
                    path.add(substr);
                    dfs(i+1);
                    //回溯 恢复现场
                    path.remove(path.size()-1);
                }
            }
        }
        public static boolean isPalindrome(String str){
            int left=0;
            int right=str.length()-1;
            while(left<right){
                if(str.charAt(left)!=str.charAt(right)){
                    return false;
                }
                left++;
                right--;
            }
            return true;
        }

    public static void main(String[] args) {
        String s="aab";
        List<List<String>> partition = partition(s);
        System.out.println(partition);

    }
    }

